﻿
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.GreedyCode
{
    class Simple
    {
        //==========================================力扣455 分发饼干
        //假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
        //对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。
        //如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
        public int FindContentChildren(int[] g, int[] s)
        {//思路：局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩
            //尝试使用贪心策略，先将饼干和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口打的
            //也可以小饼干优先喂给胃口小的 反过来就行了
            Array.Sort(g);
            Array.Sort(s);
            int result = 0;
            int index = s.Length - 1;//饼干数组下标
            for (int i = g.Length - 1; i >= 0; i--)
            {
                if (index >= 0 && s[index] >= g[i])
                {
                    result++;
                    index--;
                }
            }
            return result;

        }

        //======================================力扣122 买卖股票的最佳时机2
        //给定一个数组prices，其中prices[i]是一支给定股票第i天的价格
        //设计一个算法来计算你所能获取的最大利润，你可以尽可能的完成多次交易（多次买卖一支股票）
        //你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
        public int MaxProfit(int[] prices)
        {//贪心算法
            //局部最优：收集每天的正利润，全局最优：求得最大利润。
            int result = 0;
            for(int i = 1;i<prices.Length;i++)//第二天开始才有利润
            {
                result += Math.Max(prices[i] - prices[i - 1], 0);
            }
            return result;
        }

        //=======================================力扣714 买卖股票的最佳时机含手续费
        //给定一个整数数组prices，其中prices[i]是一支给定股票第i天的价格,整数fee代表了交易股票的手续费
        //你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
        //返回获得利润的最大值。
        //注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
        public int MaxProfit(int[] prices, int fee)
        {//贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。

            int result = 0;
            int minPrice = prices[0];//记录最低价格
            for(int i = 1;i<prices.Length;i++)
            {
                //前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
                if (prices[i] < minPrice)
                    minPrice = prices[i];

                //保持原有状态（因为此时买则不便宜，卖则亏本）
                if (prices[i] > minPrice && prices[i] <= minPrice + fee)
                    continue;

                //// 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
                if (prices[i] > minPrice + fee)
                {
                    result += prices[i] - minPrice - fee;
                    //收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
                    minPrice = prices[i] - fee;
                }
            }
            return result;
        }



        //=====================================力扣1005 K次取反后最大化的数组和
        //给定一个整数数组A，我们只能用以下方法修改数组：
        //我们选择某个索引i并将A[i]替换为-A[i]，然后总共重复这个过程k次。(我们可以多次选择同一个索引i）
        //以这种方式修改数组后，返回数组可能的最大和。
        public int LargestSumAfterKNegations(int[] nums, int k)
        {//贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
            //局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大
            for(int i = 0;i<nums.Length;i++)
            {//将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
                for(int j = i+1;j<nums.Length;j++)
                {
                    if(Math.Abs(nums[i]) < Math.Abs(nums[j]))
                    {
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                    }
                }
            }

            for(int i = 0;i<nums.Length;i++)
            {//从前向后遍历，遇到负数将其变为正数，同时K--
                if (nums[i] < 0 && k > 0)
                {
                    nums[i] *= -1;
                    k--;
                }
            }

            if (k % 2 == 1)//如果K还大于0，那么反复转变数值最小的元素，将K用完
                nums[nums.Length - 1] *= -1;

            int result = 0;
            foreach (int a in nums)//求和
                result += a;

            return result;
        }

        //===============================力扣860 柠檬水找零
        //在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
        //每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
        //注意，一开始你手头没有任何零钱。
        //给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
        public bool LemonadeChange(int[] bills)
        {
            int five = 0, ten = 0, twenty = 0;
            foreach(int bill in bills)
            {
                if (bill == 5)//账单是5，直接收下。
                    five++;

                if (bill == 10)
                {//账单是10，消耗一个5，增加一个10
                    if (five <= 0)
                        return false;
                    five--;
                    ten++;
                }

                if (bill == 20)
                {//账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
                    if (five > 0 && ten > 0)
                    {//局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
                        five--;
                        ten--;
                        twenty++;
                    }
                    else if (five >= 3)
                    {
                        five -= 3;
                        twenty++;
                    }
                    else
                        return false;
                }
            }
            return true;
        }




    }
}
